/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/interval-minimum-number
   @Language: C++
   @Datetime: 16-02-09 05:55
   */

/**
 * Definition of Interval:
 * struct Interval {
 *     int start, end;
 *     Interval(int start, int end) {
 *         this->start = start;
 *         this->end = end;
 *     }
 * }
 */

class Solution {
	struct SegmentTreeNode{
		int start, end, val;
		SegmentTreeNode *left, *right;
		SegmentTreeNode(int start, int end, int val){
			this->start=start;
			this->end=end;
			this->val=val;
			this->left=this->right=NULL;
		}
	};
	SegmentTreeNode *build(vector<int> &A, int start, int end){
		if(A.size()<1 || start>end) return NULL;
		SegmentTreeNode *root=new SegmentTreeNode(start, end, A[start]);
		if(start==end) return root;
		root->left=build(A,start,(start+end)/2);
		root->right=build(A,(start+end)/2+1,end);
		root->val=min(root->left->val,root->right->val); // minival
		return root;
	}
	int query(SegmentTreeNode *root, int start, int end){
		if(root==NULL || start>root->end || end<root->start) return 0;
		if(start==root->start && end==root->end) return root->val;
		int mid=(root->start+root->end)/2;
		if(start>mid) return query(root->right,start,end);
		if(end<=mid) return query(root->left,start,end);
		return min(query(root->left,start,mid),query(root->right,mid+1,end));
	}
	void destroy(SegmentTreeNode *root){
		if(root==NULL) return;
		destroy(root->left);
		destroy(root->right);
		delete root;
	}
public:
	/**
	 * @param A: An integer array
	 * @param queries: An query list
	 * @return: The result list
	 */
	vector<int> intervalMinNumber(vector<int> &A, vector<Interval> &queries) {
		// write your code here
		if(queries.size()<1) return {};
		SegmentTreeNode *root=build(A,0,A.size()-1);
		vector<int> v(queries.size(),0);
		for(int i=0; i<queries.size(); ++i){
			v[i]=query(root,queries[i].start,queries[i].end);
		}
		destroy(root);
		return v;
	}
};
